Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

  1. Given nums = [2, 7, 11, 15], target = 9,
  3. Because nums[0] + nums[1] = 2 + 7 = 9,
  4. return [0, 1].

The return format had been changed to zero-based indices. Please read the above updated description carefully.

The idea:

We should be able to find the two numbers by scanning the array once (from left to right). We use a hashmap to store the value:index for each number, at i-th position, we check if the value of target - nums[i] exsists in the hashmap and they have different positions.

Time complexity: O(n)

Space complexity: O(n)

Solution - Java:

  1. public class Solution {
  2.   public int[] twoSum(int[] nums, int target) {
  3.     Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  5.     for (int i = 0; i < nums.length; i++) {
  6.       int num1 = nums[i];
  7.       int num2 = target - num1;
  9.       if (map.containsKey(num2)) {
  10.         return new int[]{map.get(num2) + 1, i + 1};
  11.       }
  13.       if (!map.containsKey(num1)) {
  14.         map.put(num1, i);
  15.       }
  16.     }
  18.     return new int[]{-1, -1};
  19.   }
  20. }

Solution - JavaScript:

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number[]}
  5.  */
  6. var twoSum = function(nums, target) {
  7.   var i, map = {};
  9.   for (i = 0; i < nums.length; i++) {
  10.     var key = target-nums[i];
  12.     if (key in map && i != map[key]) {
  13.       return [i, map[key]];
  14.     }
  16.     map[nums[i]] = i;
  17.   }
  19.   return [-1, -1];
  20. };